/*
    Insert Node in a doubly sorted linked list 
    After each insertion, the list should be sorted
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev
   }
*/
Node* SortedInsert(Node *head,int data)
{
    // Complete this function
    // Do not write the main method.
    if(head == NULL) {
        head = new Node();
        head->data = data;
        head->next = head->prev = NULL;
    } else if(data < head->data) {
        Node *pn = head;
        head = new Node();
        head->data = data;
        head->next = pn;
        pn->prev = head;
        head->prev = NULL;
    } else {
        Node *n = head;
        while(n->next != NULL && n->next->data <= data)
            n = n->next;
        Node *pn = n->next;
        n->next = new Node();
        n->next->data = data;
        n->next->next = pn;
        if(pn != NULL)
            pn->prev = n->next;
        n->next->prev = n;
    }
    return head;
}